n=100;
m=100;
p=[29274,72311,77257,2681,52879,96494,10756,66547,1205,41308,29018,71254,9864,68500,23973,93332,66008,41372,11063,12304,81534,84600,4255,2177,85286,33213,86669,87206,98161,22301,81536,17720,98486,75025,84374,10715,65737,89430,89416,40550,88811,75214,72454,86563,457,71049,62895,27851,69678,32267,78528,59355,31926,53510,93794,18561,30866,41662,85511,24745,57361,19172,6469,7068,73108,64315,83760,94612,65969,93170,43683,37145,55792,50418,25671,21225,4951,99066,23477,56290,24033,96346,12166,59376,86403,2470,96728,37932,84415,6816,44381,69162,53963,10223,97617,69219,4851,14714,84173,34676];
road=[|1,2|
2,3|
3,4|
4,5|
5,6|
6,7|
7,8|
8,9|
9,10|
10,11|
11,12|
12,13|
13,14|
14,15|
15,16|
16,17|
17,18|
18,19|
19,20|
20,21|
21,22|
22,23|
23,24|
24,25|
25,26|
26,27|
27,28|
28,29|
29,30|
30,31|
31,32|
32,33|
33,34|
34,35|
35,36|
36,37|
37,38|
38,39|
39,40|
40,41|
41,42|
42,43|
43,44|
44,45|
45,46|
46,47|
47,48|
48,49|
49,50|
50,51|
51,52|
52,53|
53,54|
54,55|
55,56|
56,57|
57,58|
58,59|
59,60|
60,61|
61,62|
62,63|
63,64|
64,65|
65,66|
66,67|
67,68|
68,69|
69,70|
70,71|
71,72|
72,73|
73,74|
74,75|
75,76|
76,77|
77,78|
78,79|
79,80|
80,81|
81,82|
82,83|
83,84|
84,85|
85,86|
86,87|
87,88|
88,89|
89,90|
90,91|
91,92|
92,93|
93,94|
94,95|
95,96|
96,97|
97,98|
98,99|
99,100|];
request=[|21,1,76,1|
33,1,31,1|
25,0,51,0|
37,1,62,0|
39,1,21,1|
7,0,98,1|
50,0,88,1|
74,1,56,0|
32,0,47,0|
70,0,25,0|
51,0,48,0|
87,0,98,0|
36,1,23,0|
83,1,80,0|
28,1,8,1|
6,0,91,0|
17,1,71,0|
72,0,3,1|
84,1,69,0|
81,1,48,1|
34,1,1,1|
92,1,52,1|
29,0,88,0|
92,1,86,1|
79,1,82,1|
30,1,53,0|
43,0,63,0|
7,1,61,0|
81,1,38,1|
28,0,24,0|
61,0,55,0|
30,1,11,0|
22,0,42,1|
40,0,63,1|
95,1,11,0|
42,1,84,0|
16,1,13,1|
76,1,83,0|
92,1,7,1|
62,0,56,1|
30,1,56,1|
1,1,39,1|
96,0,73,1|
96,0,89,0|
8,1,52,0|
57,0,25,1|
82,0,53,0|
10,1,86,1|
53,0,34,1|
55,1,26,0|
15,1,12,0|
49,0,69,0|
28,0,25,1|
75,0,18,0|
53,1,56,1|
57,0,96,1|
43,1,64,1|
46,0,27,1|
66,1,24,0|
36,0,37,0|
11,1,5,1|
7,1,2,0|
10,0,82,0|
59,1,91,1|
68,0,64,0|
23,0,16,1|
9,1,35,1|
94,1,81,1|
1,1,13,1|
52,1,93,1|
82,0,34,0|
57,1,89,1|
47,0,55,1|
49,0,4,0|
42,0,43,1|
81,1,67,1|
12,1,99,1|
60,1,41,0|
34,0,61,1|
57,1,81,0|
71,0,5,0|
97,1,36,1|
92,1,39,1|
93,0,4,1|
53,1,97,0|
69,0,76,0|
44,1,10,0|
93,1,25,0|
3,1,92,0|
17,1,38,1|
50,1,26,1|
91,0,56,1|
13,0,41,0|
91,0,6,0|
23,0,50,0|
78,1,18,1|
12,0,22,0|
38,1,2,0|
56,1,30,1|
30,1,45,0|];